Masala #0452
Ajoyib ketma-ketliklar
Uzungligi \(m\) ga teng \(b_1,b_2,...,b_m\) ketma-ketlik ajoyib bo’lishi uchun, uning ikki chetidagi elementlari qolgan \(m-2\) ta elementdan qat’iy katta bo’lishi kerak. Boshqacha qilib aytganda \(\min (b_1,b_m) > \max (b_2,b_3,...,b_{m-1})\) shart bajarilishi kerak. E’tibor bering, \(m \leq 2\) bo’lsa ketma-ketlik ajoyib hisoblanadi.
Sizga uzunligi \(n\) ga teng \(a\) massiv berilgan. Sizning vazifangiz massivni bir nechta oraliqlarga bo’lish, bunda har bir element aynan bitta oraliqqa tegishli bo’ladi va har bir oraliqdagi elementlar ajoyib ketma-ketlikni tashkil qiladi. Yuqoridagi shartlar bajarilishi uchun minimal oraliqlar sonini toping.
Birinchi qatorda \(n\) kiritiladi \((1 \leq n \leq 200000)\)
Ikkinchi qatorda \(a_1, a_2, ..., a_n\) kiritiladi \((1 \leq a_i \leq 10^9)\).
Bitta qatorda minimal oraliqlar sonini chiqaring.
| # | input.txt | output.txt |
|---|---|---|
| 1 |
9 4 1 5 3 9 5 7 8 9 |
3 |
| 2 |
3 2 2 2 |
2 |
| 3 |
3 3 1 2 |
1 |
Birinchi misolda massivni \([4,1,5], [3], [9,5,7,8,9]\) ko’rinishida bo’lish mumkin.
Ikkinchi misolda massivni \([2, 2], [2]\) ko’rinishida bo’lish mumkin.
Uchinchi misolda butun massiv ajoyib hisoblanadi, demak minimal javob 1.
Telegram kanalimizga obuna bo'ling